﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//一个很简单的想法，用自己标记自己
//但是题目要求不修改数组
public class Solution287
{//一个很简单的想法，用自己标记自己
    //修改第二次的时候停止就可以了
    public int FindDuplicate2(int[] nums)
    {
        int res = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            int flagIndex = nums[i];//要标记的
            if (flagIndex < 0)
            {
                //取绝对值
                flagIndex = -flagIndex;
            }
            //修改
            if (nums[flagIndex] < 0)
            {
                res = -nums[flagIndex]; break;
            }
            else
            {
                nums[flagIndex] = -nums[flagIndex];//标记负号
            }


        }


        return res;
    }
    //使用一个flag
    public int FindDuplicate3(int[] nums)
    {
        Array.Sort(nums);//修改了原数组
        int flag = nums[0];
        int res = 0;
        for (int i = 1; i < nums.Length; i++)
        {

            if (flag != nums[i])
            {
                flag = nums[i];
            }
            else
            {
                res = flag;
            }


        }

        return res;
    }
    //暴力一下,超时
    public int FindDuplicate4(int[] nums)
    {
        int res = -1;
        for (int i = 0; i < nums.Length; i++)
        {

            for (int j = i + 1; j < nums.Length; j++)
            {

                if (nums[j] == nums[i])
                {
                    res = nums[j];
                }

            }

        }

        return res;
    }


    //观察前缀法,顺序查找,超时，后面使用二分
    public int FindDuplicate5(int[] nums)
    {
        int cnt = 0;//记录小于等于自己的数cnt有几个
        //重复的数和比自己大的数，num<cnt[num]
        int res = nums.Length + 2;
        for (int i = 0; i < nums.Length; i++)
        {

            for (int j = 0; j < nums.Length; j++)
            {

                if (nums[j] <= nums[i])
                {
                    cnt++;
                }

            }

            if (cnt > nums[i])
            {
                Console.WriteLine("cnt:   " + cnt + "  nums[i]:   " + nums[i]);
                res = Math.Min(res, nums[i]);
            }
            cnt = 0;
        }

        return res;
    }

    public int FindDuplicate6(int[] nums)
    {
       
        //重复的数和比自己大的数，num<cnt[num]
        int res = -1;

        int left = 1;
        int right = nums.Length;
        int mid = (left + right) / 2;//mid的作用不是为了找数组的中间数，而是代表范围[1，n]的中间

        while (left <= right)
        {
            int cnt = 0;//记录小于等于自己的数cnt有几个

            for (int j = 0; j < nums.Length; j++)
            {

                if (nums[j] <= mid)
                {
                    cnt++;
                }

            }

            if (cnt > mid)
            {
                //在左侧区间
                right = mid - 1;
                res = mid;//在左侧才更新res????
                //这一步相当于 res = Math.Min(res, nums[i]);
                //找到cnt[num]>num里面最小的
            }
            else
            {
                left = mid + 1;
            }
           
            mid = (left + right) / 2;
            Console.WriteLine("left:  " + left + "  right:  " + right + "  mid:  " + mid);
            

        }

        return res;
    }
    //快慢指针
    //快指针追上慢指针
    //把数组变成带有环的链表
    public int FindDuplicate(int[] nums)
    {

        int low = 0;
        int fast = 0;
        low = nums[low];
        fast = nums[nums[fast]];

        while (low!=fast)
        {


            low = nums[low];
            fast = nums[nums[fast]];

        }
        int start = 0;
        while (start != low) {
            low = nums[low];
            start = nums[start];
        }

        return nums[start];
    }
}
class Program287
{
    static void Main287(string[] args)
    {

        Solution287 solution287 = new Solution287();
        int[] nums = [1, 3, 4, 2, 2];
        //int[] nums = [3, 3, 3, 3, 3];
        //int[] nums = [3, 1, 3, 4, 2];
        int res = solution287.FindDuplicate(nums);
        Console.WriteLine(res);
    }
}